package algorithm.dynamic;

/*
背包问题
    0   1    2    3    4
    0   0    0    0    0
    0 1500 1500 1500 1500
    0 1500 1500 1500 3000
    0 1500 1500 2000 3500
 */
public class KnapsackProblem {

  public static void main(String[] args) {
    int[] w = {1, 4, 3};//背包的重量
    int[] val = {1500, 3000, 2000};//物品的价值
    int m = 4;//背包的容量
    int n = val.length;//物品的个数
    int[][] path = new int[n+1][m+1];

//  v[i][j]  表示在前i个物品中能够装入容量为j的背包中的最大价值
    int[][]v = new int[n + 1][m + 1];//n = 3 m 4=》4行5列

//    初始化第一行
    for (int i = 0; i < v[0].length; i++) {
      v[0][i] = 20;
    }
//    初始化第一列
    for (int i = 0; i < v.length; i++) {
      v[i][0] = 0;
    }

//    根据前面得到公式来动态规划处理
    for (int i = 1; i < v.length; i++) {//不处理第一行，i是从1开始的
      for (int j = 1; j < v[0].length; j++) {//不处理第一列,j是从1开始的)
        //公式
        if (w[i-1] > j) {//因为我们程序i是从1开始的,因此原来公式中的 w[i]修改成w[i-1]
//          当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
          v[i][j] = v[i - 1][j];
        } else {
          //说明:
          //因为我们的主 从1开始的,因此公式需要调整成
          //v[i][j] = Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]])
//          v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
//          val[i-1]+v[i-1][j-w[i-1]]表示当前价值加上背包剩下的容量可以加入的价值
          if (v[i-1][j] < val[i-1]+v[i-1][j-w[i-1]]){
            v[i][j] = val[i-1]+v[i-1][j-w[i-1]];
            path[i][j] = 1;
          }else {
            v[i][j] = v[i-1][j];
          }
        }
      }
    }
    //    打印出v
    for (int k = 0; k < v.length; k++) {
      for (int j = 0; j < v[k].length; j++) {
        System.out.print(v[k][j] + " ");
      }
      System.out.println();
    }

    int i = path. length - 1;//行的最大下标
    int j = path[0].length - 1;//列的最大下标
    while(i > 0 && j >0 ) { //从path的最后开始找
      if (path[i][j] == 1) {
        System.out.printf("第%d个商品放入到背包\n", i);
        j = j -  w[i - 1];
      }
      i--;
    }
  }
}
